Image processing systems typically include an input device such as a scanner and a computer system that is equipped with document applications for storing and editing scanned electronic documents and an output device such as a printing system for rendering documents. The computer system is operated by a user to edit or view scanned "softcopy" digital images on a monitor of the computer system. The user can subsequently generate "hardcopy" reproductions of the softcopy images by instructing the computer system to provide the processed electronic image to a selected printing device. Advances in printing technology together with advances in computer system technology are helping image processing systems become more pervasive in desk-top publishing and business applications. Ink jet, thermal-transfer and xerographic color are examples of printing technologies that are making moderate resolution affordable.
Electronic images or "softcopy" images processed by desk-top publishing applications consist of two dimensional arrays of picture elements (pixels) or image signals. Historically small computer memories requires the use of intermediate disk buffers to rotate an electronic image of reasonable size. However, with the availability of larger computer memories, desk-top publishing applications can store entire electronic images in real memory. Even with large real memory allocations, there is not always sufficient memory to store both an original image and a rotated image. In some systems for example, available computer memory is large enough to contain one electronic image but not large enough to contain both an original image and a rotated image. In such instances rotating an electronic image in place, that is, within its own buffer and without the use of significant intermediate memory or auxiliary memory is desirable. Rotating an image in place for any arbitrary rotation however is not always possible since the image memory allocation of a rotated image can be larger than the memory allocation of an original image. Ninety degrees rotation of an original image, however, results in a rotated image having equal memory allocation as the original image.
To rotate an electronic image in place, requires that sequences of replacement operations are performed to an electronic image that is stored in an image buffer. Each replacement operation of a sequence must be performed so that each replacement operation does not erase pixels in the image buffer not already transferred. An analytical solution to the problem of finding the starting locations of the replacement sequences for ninety degree rotations, pixel by pixel, is given by Pall et al. in "A Problem in Abelian Groups with Application to the Transposition of a Matrix on an Electronic Computer", Math. Comp. 14 (1960), 189-192.